package com.explorati.MaxHeap;

/**
 * 堆的性质：父节点大于任意一个子节点
 * 
 * @author explorati
 *
 * @param <E>
 */
public class MaxHeap<E extends Comparable<E>> {

	private Array<E> data;

	public MaxHeap(int capacity) {
		data = new Array<>(capacity);
	}

	public MaxHeap() {
		data = new Array<>();
	}

	public MaxHeap(E[] arr) {
		data = new Array<>(arr);
		for (int i = parent(arr.length - 1); i >= 0; i--) {
			siftDown(i);
		}
	}

	// 返回堆中的元素个数
	public int size() {
		return data.getSize();
	}

	// 返回一个布尔值, 表示堆中是否为空
	public boolean isEmpty() {
		return data.isEmpty();
	}

	// 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
	private int parent(int index) {
		if (index == 0)
			throw new IllegalArgumentException("index-0 doesn't have parent.");
		return (index - 1) / 2;
	}

	// 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
	private int leftChild(int index) {
		return index * 2 + 1;
	}

	// 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
	private int rightChild(int index) {
		return index * 2 + 2;
	}

	// 向堆中添加元素
	public void add(E e) {
		data.addLast(e);
		siftUp(data.getSize() - 1);
	}

	// 对比当前元素和父节点的元素的大小，若父节点的比他小，则交换
	private void siftUp(int k) {
		while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
			data.swap(k, parent(k));
			k = parent(k);
		}
	}

	// 看堆中的最大元素
	public E findMax() {
		if (data.getSize() == 0) {
			throw new IllegalArgumentException("Can not findMax when heap is empty.");
		}
		return data.get(0);
	}

	// 取出堆中最大元素
	public E extractMax() {
		E ret = findMax();

		data.swap(0, data.getSize() - 1);
		data.removeLast();
		siftDown(0);

		return ret;
	}

	private void siftDown(int k) {
		while (leftChild(k) < data.getSize()) {
			int j = leftChild(k);
			if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
				j = rightChild(k);
			}
			// data[j] 是 leftChild和rightChild中的最大值
			if (data.get(k).compareTo(data.get(j)) >= 0) {
				break;
			} else {
				data.swap(k, j);
				k = j;
			}
		}
	}

	// replace：取出最大元素后，放入一个新元素
	// 实现：可以先extractMax,再add，两次O(logn)的操作
	// 实现：可以直接将堆顶元素替换以后Sift Down，一次O(logn)的操作
	// 取出堆中最大元素，并替换成元素e
	public E replace(E e) {
		E ret = data.get(0);
		data.set(0, e);
		siftDown(0);
		return ret;
	}

	// heapify：将任意数组整理成堆的形状
	// 第一种想法：一个一个添加元素进堆
	// 第二种方法：找到第一个非叶子节点，向上循环，每个节点siftDown
	public void heapify(int[] arr) {
		for (int i = (arr.length - 1) / 2; i >= 0; i--) {
			siftDown(i);
		}
	}

}
